//BAO TAM VO
#include "my_malloc.h"

/* You *MUST* use this macro when calling my_sbrk to allocate the
 * appropriate size. Failure to do so may result in an incorrect
 * grading!
 */
#define SBRK_SIZE 2048
//#define DEBUG

/* If you want to use debugging printouts, it is HIGHLY recommended
 * to use this macro or something similar. If you produce output from
 * your code then you will receive a 20 point deduction. You have been
 * warned.
 */
#ifdef DEBUG
#define DEBUG_PRINT(x) printf x
#define DEBUG_PRINT_FREELIST print_freelist();
#else
#define DEBUG_PRINT(x)
#define DEBUG_PRINT_FREELIST
#endif

#define FREELIST_SIZE 8
#define MIN_BLOCK_SIZE 16
#define MAX_BLOCK_SIZE SBRK_SIZE
/* make sure this always points to the beginning of your current
 * heap space! if it does not, then the grader will not be able
 * to run correctly and you will receive 0 credit. remember that
 * only the _first_ call to my_malloc() returns the beginning of
 * the heap. sequential calls will return a pointer to the newly
 * added space!
 * Technically this should be declared static because we do not
 * want any program outside of this file to be able to access it
 * however, DO NOT CHANGE the way this variable is declared or
 * it will break the autograder.
 */
void* heap;

/* our freelist structure - this is where the current freelist of
 * blocks will be maintained. failure to maintain the list inside
 * of this structure will result in no credit, as the grader will
 * expect it to be maintained here.
 * Technically this should be declared static for the same reasons
 * as above, but DO NOT CHANGE the way this structure is declared
 * or it will break the autograder.
 */
metadata_t* freelist[FREELIST_SIZE];
/**** SIZES FOR THE FREE LIST ****
 * freelist[0] -> 16
 * freelist[1] -> 32
 * freelist[2] -> 64
 * freelist[3] -> 128
 * freelist[4] -> 256
 * freelist[5] -> 512
 * freelist[6] -> 1024
 * freelist[7] -> 2048
 */

static int find_list_index(size_t data_size);
static void setup_freelist(metadata_t* largest_block_ptr);
static int is_empty(int freelist_index);
static void add_to_head(metadata_t* block);
static int merge_block(metadata_t *block);
static metadata_t* remove_block(metadata_t* block);
static metadata_t* remove_head(int freelist_index);
static metadata_t* find_buddy(metadata_t *block);
static int split_block(int start_index, int end_index);
static int log_base2(double x);

/*
 * return the ceiling of log base 2 of x
 */
static int log_base2(double x)
{
	DEBUG_PRINT(("\ncalculating log2 of %lf", x));
	int result = 0;
	int to_multiply = 1;
	while(to_multiply < x)
	{
		to_multiply *= 2;
		result++;
	}
	DEBUG_PRINT(("\nlog2 of %lf is %d ", x, result));

	return result;
}

/*
 * set up the list by initializing the largest block
 */
static void setup_freelist(metadata_t* largest_block_ptr)
{
	freelist[7] = largest_block_ptr;
	freelist[7]->in_use = 0;
	freelist[7]->next = NULL;
	freelist[7]->prev = NULL;
	freelist[7]->size = SBRK_SIZE;
}

/*
 * return 1 if the list at the index is empty, 0 otherwise
 */
static int is_empty(int freelist_index)
{
	return (freelist[freelist_index] == NULL);
}

/*
 * add a block to the head of its list
 */
static void add_to_head(metadata_t* block)
{
	DEBUG_PRINT(("\n-adding to head this block: %ld", (long)block));

	int list_index = find_list_index(block->size - sizeof(metadata_t));
	DEBUG_PRINT(("\n-found its destination at index: %d", list_index));

	if(freelist[list_index] != NULL)
	{
		block->next = freelist[list_index];
		freelist[list_index]->prev = block;
	}
	freelist[list_index] = block;

}
/*
 * remove and return the head of the list at the index
 */
static metadata_t* remove_head(int freelist_index)
{
	metadata_t *head = freelist[freelist_index];

	//make the next node the new head and set the new head's prev to NULL
	freelist[freelist_index] = head->next;
	if(freelist[freelist_index] != NULL) freelist[freelist_index]->prev = NULL;
	head->next = NULL;

	return head;
}

/*
 * remove a block from its list and return the block just removed
 */
static metadata_t* remove_block(metadata_t* block)
{
	DEBUG_PRINT(("\n-begin removing block: %ld", (long)block));
	//if the block is not the head
	if(block->prev != NULL)
	{
		DEBUG_PRINT(("\n-block is not head"));

		block->prev->next = block->next;
		block->next->prev = block->prev;
		block->prev = NULL;
		block->next = NULL;
	}
	else //the block can be the head or a stand alone block
	{
		DEBUG_PRINT(("\n-block is either head or free"));
		DEBUG_PRINT(("\n-go and look for the index of the list of the block"));
		int list_index = find_list_index(block->size - sizeof(metadata_t));
		//if the block is the head of its list then remove, if not, then nothing needs to be done
		DEBUG_PRINT(("\n-list_index is %d",list_index));
		if(freelist[list_index] == block){
			DEBUG_PRINT(("\n-block is head"));
			freelist[list_index] = block->next;
			if(block->next != NULL) block->next->prev = NULL;
			block->next = NULL;
		}

	}

	return block;
}

/*
 * go top down to split a block at start_index to the size at the end_index
 * return 1 if successful, 0 otherwise
 * contract: all the lists from start_index to end_index is empty
 */
static int split_block(int start_index, int end_index)
{
	DEBUG_PRINT(("\nsplit_block begin :: start_index %d, end_index %d", start_index, end_index));
	DEBUG_PRINT_FREELIST;
	if(start_index == 0 || start_index > FREELIST_SIZE - 1) return 0;
	if(is_empty(start_index)) return 0;
	if(end_index < 0 || end_index > FREELIST_SIZE - 1) return 0;

	//base case, nothing to be done
	if(start_index <= end_index) return 0;
	//recursive step occurs when start_index > end_index

	//get the head of the list
	metadata_t *to_split = remove_head(start_index);
	DEBUG_PRINT(("\n-the block to split is located at %ld", (long)to_split));

	//compute child_size = parent size / 2
	short child_size = to_split->size/2;

	//child_a is the first child so it receives the address of the parent
	metadata_t *child_a = to_split;
	//child_b is the second child so it address is parent address + child_size
	metadata_t *child_b = (metadata_t *)((char *)to_split + child_size);

	DEBUG_PRINT(("\n-child a is located at %ld", (long)child_a));
	DEBUG_PRINT(("\n-child b is located at %ld", (long)child_b));
	DEBUG_PRINT(("\n-child a and b has size %d", child_size));
	child_a->in_use = 0;
	child_a->prev = NULL;
	child_a->next = child_b;
	child_a->size = child_size;

	child_b->in_use = 0;
	child_b->prev = child_a;
	child_b->next = NULL;
	child_b->size = child_size;

	//initialize the list of smaller size
	freelist[start_index - 1] = child_a;

	split_block(start_index - 1, end_index);

	return 1;

}


//compute the appropriate index on the free_list that has the blocks large enough for the data
static int find_list_index(size_t data_size)
{
	DEBUG_PRINT(("\nlooking for list index for data size of %ld", data_size));
	double block_size = data_size + sizeof(metadata_t);
	DEBUG_PRINT(("\nactual size needs to allocate is %lf", block_size));
	return log_base2(block_size/MIN_BLOCK_SIZE);
}


/*
 *return the pointer to the buddy of the current block
 */
static metadata_t* find_buddy(metadata_t *block)
{
	int n = (int)(log_base2((double)block->size));

	metadata_t* buddy = (metadata_t *)((((long)block - (long)heap) ^ (1 << n)) + (long)heap);
	if(buddy->size != block->size) return NULL;
	/*
	if(buddy < block)
	{
		if((char *)buddy + buddy->size != (char *)block) return NULL;
	}
	else
	{
		if((char *)buddy - buddy->size != (char *)block) return NULL;
	}
	*/
	return buddy;
}

/*
 * return true if merge is successful
 */
static int merge_block(metadata_t *block)
{
	DEBUG_PRINT(("\n\nbegin merging of block %ld", (long)block));
	metadata_t* buddy = find_buddy(block);
	DEBUG_PRINT(("\n-found buddy at %ld", (long)buddy));

	if(buddy == NULL || buddy->in_use || block->size == MAX_BLOCK_SIZE)
	{

		DEBUG_PRINT(("\n-fail to merge block, add it back to list"));
		//can't merge the block so add the free block to its list
		add_to_head(block);
		DEBUG_PRINT_FREELIST;

		return 0;
	}
	DEBUG_PRINT_FREELIST;

	DEBUG_PRINT(("\n-removing buddy from its list"));
	remove_block(buddy);
	//the address of the new block is the address of whichever block has the smaller address
	metadata_t* new_block = (block < buddy) ? block : buddy;
	new_block->size = block->size * 2;
	merge_block(new_block);
	return 1;
}

/*
 * print the representation of the list
 */
void print_freelist()
{
	printf("\nfreelist status");
	for(int i = 0; i < FREELIST_SIZE; i++)
	{
		printf("\n%d", i);
		if(!is_empty(i))
		{
			metadata_t *block = freelist[i];
			while(block != NULL)
			{
				printf(" |");
				printf("%ld",(long)block);

				for(int i2 = 0; i2 < i; i2++)
				{
					printf("_");
				}
				printf("|");
				block = block->next;
			}
		}
	}
}

void* my_malloc(size_t size)
{
	DEBUG_PRINT(("\n\nmy_malloc begin, size: %ld", size));
	/*TODO FIX ME *///
	if(size+sizeof(metadata_t) > SBRK_SIZE)
	{
		ERRNO = SINGLE_REQUEST_TOO_LARGE;
		return NULL;
	}
	if(size <= 0)
	{
		return NULL;
	}

	static int first_call = 1;
	if(first_call)
	{
		DEBUG_PRINT(("\n-first call, set up heap"));
		DEBUG_PRINT(("\n-before setup, heap is located at %p", heap));
		heap = my_sbrk(SBRK_SIZE);
		if(heap == (void *)-1) return NULL; //return null if there's no memory left in the system, disregard this first call
		first_call = 0;
		setup_freelist(heap);
		DEBUG_PRINT(("\n-done setup, heap is located at %p", heap));
		DEBUG_PRINT(("\n-done setup, largest block (should be located at heap) is located at %p", (void*)freelist[7]));
	}

	//compute the appropriate index on the free_list that has the blocks large enough for the data
	int index = find_list_index(size);
	DEBUG_PRINT(("\n-expected list index: %d", index));
	DEBUG_PRINT(("\n-the block at expected index is %p",(void*)freelist[index]));

	//get the address of the block that will be given to the user
	//if the current index has no blocks available
	if(freelist[index] == NULL)
	{
		//find the free list index that contains larger blocks to split up
		int split_block_result = 0;
		DEBUG_PRINT(("\n-no block available at expected index, begin looping to find the smallest available block"));
		for(int larger_block_list_index = index + 1; larger_block_list_index < FREELIST_SIZE; larger_block_list_index++)
		{

			DEBUG_PRINT(("\n--index is %d", larger_block_list_index));
			if(!is_empty(larger_block_list_index))
			{
				DEBUG_PRINT(("\n--the most available block is at index %d", larger_block_list_index));
				split_block_result = split_block(larger_block_list_index, index);
				break;
			}
		}

		DEBUG_PRINT(("\n-result of split block is %d", split_block_result));

		//if the for loop does not successfully split_block, then there is no block available for splitting
		//we have to extend the heap
		if(!split_block_result)
		{
			DEBUG_PRINT(("\n-fail to find available block in current heap, expanding"));

			//handle exception by extending the heap
			void *new_heap_space = my_sbrk(size);
			if(new_heap_space == (void *)-1)
			{
				DEBUG_PRINT(("\n-out of memory, setting error, return NULL"));
				ERRNO = OUT_OF_MEMORY;
				return NULL;
			}
			DEBUG_PRINT(("\n-re-setup free list, new space is located at %ld", (long)new_heap_space));
			//re-init the largest block
			setup_freelist(new_heap_space);
			//split the largest block up until get to the desired size
			split_block(FREELIST_SIZE - 1,index);
		}

	}


	metadata_t *block = remove_head(index);
	block->in_use = 1;
	void *result = (void *)(block + 1);
	DEBUG_PRINT(("\nend of my_malloc, result is %ld", (long)result));
	DEBUG_PRINT_FREELIST;
	return result;

	//return NULL;
}




void* my_calloc(size_t num, size_t size)
{
  /*TODO FIX ME */
  return my_malloc(num * size);
}

void my_free(void* ptr)
{
  /*TODO FIX ME */
	DEBUG_PRINT(("\n\nbegin freeing %ld", (long)ptr));
	if(ptr == NULL) return;
	if((char *)ptr < (char *)heap - sizeof(metadata_t)) return;
	// TODO fix exception invalid ptr
	metadata_t* to_free = (metadata_t *)ptr - 1;
	if(!to_free->in_use)
	{
		DEBUG_PRINT(("\n-double free detected, writing error, aborting"));
		ERRNO = DOUBLE_FREE_DETECTED;
		return;
	}
	to_free->in_use = 0;
	merge_block(to_free);
}

void* my_memmove(void* dest, const void* src, size_t num_bytes)
{
  /* TODO FIX ME */
	if(dest == NULL || src == NULL) return dest;
	char *buffer = (char *)my_malloc(num_bytes);
	if(buffer == NULL) return dest;
	for(int i = 0; i < num_bytes; i++)
	{
		DEBUG_PRINT(("\nmoving %c", *((char *)src + i)));
		buffer[i] = *((char *)src + i);
	}
	DEBUG_PRINT(("\nbuffer is now : %s", buffer));
	for(int i = 0; i < num_bytes; i++)
	{
		DEBUG_PRINT(("\nmoving %c", *(buffer + i)));
		*((char *)dest + i) = buffer[i];
	}
	return dest;
}
